package summary;

/**
 * @Author: 海琳琦
 * @Date: 2022/7/9 11:31
 * https://leetcode.cn/problems/is-graph-bipartite/
 */
public class Title786 {

    int n;

    boolean valid;

    private static int UNCOLORED = 0;

    private static int RED = 1;

    private static int GREEN = 2;


    public  boolean isBipartite(int[][] graph) {
        valid = true;
        n = graph.length;
        //0 未访问，队伍1，队伍2
        int[] team = new int[n];
        for (int i = 0; i < n; i++) {
            if (team[i] == UNCOLORED) {
                dfs(graph, team, i, RED);
            }
        }
        return valid;
    }

    private  void dfs(int[][] graph, int[] team, int i, int teamId) {
        team[i] = teamId;
        int otherId = teamId == RED ? GREEN : RED;
        for (int nodes : graph[i]) {
            if (team[nodes] == UNCOLORED) {
                dfs(graph, team, nodes, otherId);
            } else if (team[nodes] != otherId) {
                valid = false;
                return;
            }
            if (!valid) {
                return;
            }
        }
    }

    public static void main(String[] args) {
        int[][] arr = {{1, 3}, {0, 2}, {1, 3}, {0, 2}};
    }
}
